package com.zwj.interview.数组.双指针;


/**
 * 输入一个由正整数组成的数组和一个正整数k，请问数组中有多少个数字乘积小于k的连续子数组？
 * 例如，输入数组[10，5，2，6]，k的值为100，有8个子数组的所有数字的乘积小于100，
 * 它们分别是[10]、[5]、[2]、[6]、[10，5]、[5，2]、[2，6]和[5，2，6]
 */
public class 连续乘积小于等于目标值的子数组个数 {

    /**
     *如果两个指针之间的子数组中数字的乘积小于k，则向右移动指针P2。向右移动指针P2相当于在子数组中添加一个新的数字，
     * 由于数组中的数字都是正整数，因此子数组中数字的乘积就会变大
     * 如果两个指针之间的子数组中数字的乘积大于或等于k，则向右移动指针P1。向右移动指针P1相当于从子数组中删除最左边的数字，
     * 由于数组中的数字都是正整数，因此子数组中数字的乘积就会变小
     *
     * 由于我们的目标是求出所有数字乘积小于k的子数组的个数，一旦向右移动指针P1到某个位置时子数组的乘积小于k，
     * 就不需要再向右移动指针P1。这是因为只要保持指针P2不动，向右移动指针P1形成的所有子数组的数字乘积就一定小于k。
     * 此时两个指针之间有多少个数字，就找到了多少个数字乘积小于k的子数组
     */
    public int numSubArrayProductLessThanK(int[] nums, int k) {
        long product = 1;
        int left = 0;
        int count = 0;
        //双指针思想
        for (int right = 0; right < nums.length; ++right) {
            product *= nums[right];
            //当累计乘积大于等于k的时候，就删除子数组左边的数字
            while (left <= right && product >= k) {
                product /= nums[left++]; //随便推进left
            }
            count += right >= left ? right - left + 1 : 0;
        }
        return count;
    }



















}
